#include "GrammarAnalyze.h"
#include "ErrorHandle.h"
#include "Token.h"

#include <stack>

using namespace std;


CGrammarAnalyze::CGrammarAnalyze( std::vector<CProductionPtr>& productions )
:m_productions(productions)
{

}

CGrammarAnalyze::~CGrammarAnalyze(void)
{
}

void CGrammarAnalyze::PopulateItems()
{
	for (int i = 0; i != m_productions.size(); ++i)
	{
		int Position = 0;
		while (Position <= m_productions[i]->Length())
		{
			CItemPtr pItem = CItem::create();
			pItem->pProduction = m_productions[i];
			pItem->Position = Position;
			pItem->Reduce = Position == m_productions[i]->Length();

			if (Position == 0 && m_productions[i]->Left() == TOKEN_START_EXTENSION)
			{
				m_pStartItem = pItem;
			}

			m_Items.push_back(pItem);

			++Position;
		}
	}
}

void CGrammarAnalyze::LogItems()
{
	LOG("### CGrammarAnalyze::LogItems Start");
	for (int i = 0; i != m_Items.size(); ++i)
	{
		LOG("No.%d , Production: %s , Position: %d", i, m_Items[i]->pProduction->toString(), m_Items[i]->Position);
	}
	LOG("### CGrammarAnalyze::LogItems End\n");
}

void CGrammarAnalyze::LogProductions()
{
	LOG("### CGrammarAnalyze::LogProductions Start");
	for (int i = 0; i != m_productions.size(); ++i)
	{
		LOG("No.%d , Production: %s", i, m_productions[i]->toString());
	}
	LOG("### CGrammarAnalyze::LogProductions End\n");
}


std::vector<CParserStatusPtr> CGrammarAnalyze::Analyze()
{
	LOG("### CGrammarAnalyze::Analyze Start");

    LogProductions();

    PopulateFirst();

    LogFirst();

    PopulateFollow();

    LogFollow();

	PopulateItems();

	LogItems();

	PopulateClosures();

	LogClosures();

	PopulateParserStatusTable();

	LogParserStatus();

	LOG("### CGrammarAnalyze::Analyze End");

	return m_ParserStatusTable;
}

void CGrammarAnalyze::Closure( ItemClosure& closure )
{
    stack<CItemPtr> Stack;

    for (ItemClosure::iterator it = closure.begin(); it != closure.end(); ++it)
    {
        Stack.push(*it);
    }

    while (!Stack.empty())
    {
        CItemPtr pCurrent = Stack.top();
        Stack.pop();

        if (!pCurrent->Reduce)
        {
            Token_Type NextToken = pCurrent->pProduction->Right()[pCurrent->Position];
            if (!IS_TERMINATE_TOKEN(NextToken))
            {
                for (int i = 0 ; i != m_Items.size(); ++i)
                {
                    if (m_Items[i]->pProduction->Left() == NextToken && m_Items[i]->Position == 0)
                    {
                        if (closure.insert(m_Items[i]).second)
                        {
                            Stack.push(m_Items[i]);
                        }
                    }
                }
            }
            else if (NextToken == TOKEN_EMPTY)
            {
                for (int i = 0 ; i != m_Items.size(); ++i)
                {
                    if (m_Items[i]->pProduction == pCurrent->pProduction && m_Items[i]->Position == pCurrent->Position + 1)
                    {
                        if (closure.insert(m_Items[i]).second)
                        {
                            Stack.push(m_Items[i]);
                        }
                    }
                }
            }
        }
    }
}

CGrammarAnalyze::ItemClosure CGrammarAnalyze::Go( ItemClosure& closure, Token_Type Token )
{
    ItemClosure GoClosure;

    for (ItemClosure::iterator it = closure.begin(); it != closure.end(); ++it)
    {
        CItemPtr pItem = *it;
        if (!pItem->Reduce)
        {
            if (pItem->pProduction->Right()[pItem->Position] == Token)
            {
                for (int i = 0 ; i != m_Items.size(); ++i)
                {
                    if (m_Items[i]->pProduction == pItem->pProduction && m_Items[i]->Position == pItem->Position + 1)
                    {
                        GoClosure.insert(m_Items[i]);
                    }
                }
            }
        }
    }
    
    Closure(GoClosure);

    return GoClosure;
}

void CGrammarAnalyze::PopulateClosures()
{

    stack<ItemClosure> Stack;

    ItemClosure StartItemClosure;
    StartItemClosure.insert(m_pStartItem);

    Closure(StartItemClosure);

    Stack.push(StartItemClosure);

    while (!Stack.empty())
    {
        ItemClosure CurrentClosure = Stack.top();
        Stack.pop();

        if (find(m_Closures.begin(), m_Closures.end(), CurrentClosure) == m_Closures.end())
        {
            m_Closures.push_back(CurrentClosure);

            for (ItemClosure::iterator it = CurrentClosure.begin(); it != CurrentClosure.end(); ++it)
            {
                CItemPtr pItem = *it;
                if (!pItem->Reduce)
                {
                    ItemClosure GoClosure = Go(CurrentClosure,pItem->pProduction->Right()[pItem->Position]);

                    Stack.push(GoClosure);
                }
            }
        }
    }


}


void CGrammarAnalyze::LogClosures()
{
	LOG("### CGrammarAnalyze::LogClosures Start");
	for (int i = 0; i != m_Closures.size(); ++i)
	{
		LOG("Closure No.%d",i);
        int j = 0;
        for (ItemClosure::iterator it = m_Closures[i].begin(); it != m_Closures[i].end(); ++it)
		{
            CItemPtr pItem = *it;
			LOG("Item No.%d , Production: %s, Position: %d", j, pItem->pProduction->toString(),pItem->Position);
            ++j;
		}
	}
	LOG("### CGrammarAnalyze::LogClosures End\n");
}

/*
 *	\brief Populate the StatusTable of thr Grammar
 */

void CGrammarAnalyze::PopulateParserStatusTable()
{
    // create one status for each closure and
    // analyze the items in that closure to see what action should be taken
	for (int ClosureIndex = 0; ClosureIndex != m_Closures.size(); ++ClosureIndex)
	{
		ItemClosure& CurrentClosure = m_Closures[ClosureIndex];

		CParserStatusPtr pStatus = CParserStatus::create();
		m_ParserStatusTable.push_back(pStatus);
        
        // for each item in that closure
        for (ItemClosure::iterator it = CurrentClosure.begin(); it != CurrentClosure.end(); ++it)
		{
            bool Handled = false;

			CItemPtr pItem = *it;

			if (pItem->Reduce)
			{
                int ProductionIndex = GetProductionIndex(pItem->pProduction);


                _Action Action;
              
                if (pItem->pProduction->Left() == TOKEN_START_EXTENSION)
                {
                    Action.Action = ACTION_ACCEPT;
                }
                else
                {
                    Action.Action = ACTION_REDUCE;
                }

                Action.ProductionIndex = ProductionIndex;

                for (set<Token_Type>::iterator it = m_Follow[pItem->pProduction->Left()].begin();
                    it != m_Follow[pItem->pProduction->Left()].end();
                    ++it)
                {
                    if (!pStatus->AddAction(*it,Action))
                    {
                        throw grammar_exception() << error_message("Action conflict");
                    }
                }

                Handled = true;
			}
			else
			{
                Token_Type NextToken = pItem->pProduction->Right()[pItem->Position];
                if (NextToken == TOKEN_EMPTY)
                {
                    Handled = true;
                }
                else
                {
                    ItemClosure GoClosure = Go(CurrentClosure,NextToken);
                    for (int i = 0; i != m_Closures.size(); ++i)
                    {
                        if (m_Closures[i] == GoClosure)
                        {
                            if (IS_TERMINATE_TOKEN(NextToken))
                            {
                                _Action Action;
                                Action.Action = ACTION_SHIFT;
                                Action.StatusIndex = i;

                                if (!pStatus->AddAction(NextToken,Action))
                                {
                                    throw grammar_exception() << error_message("Action conflict");
                                }

                                Handled = true;
                            }
                            else
                            {
                                _GOTO GOTO;
                                GOTO.StatusIndex = i;
                                if (!pStatus->AddGoto(NextToken,GOTO))
                                {
                                    throw grammar_exception() << error_message("GOTO conflict");
                                }

                                Handled = true;
                            }
                        }
                    }
                }
			}

            if (!Handled)
            {
                throw grammar_exception() << error_message("Unhandled Closure");
            }
		}
	}
}

int CGrammarAnalyze::GetProductionIndex( CProductionPtr pProduction )
{
	for (int i = 0; i != m_productions.size(); ++i)
	{
		if (m_productions[i] == pProduction)
		{
			return i;
		}
	}
	return -1;
}

void CGrammarAnalyze::LogParserStatus()
{
	LOG("### CGrammarAnalyze::LogParserStatus Start");
	for (int i = 0; i != m_ParserStatusTable.size(); ++i)
	{
		LOG("Status No.%d", i);
		m_ParserStatusTable[i]->Log();
		LOG("");
	}
	LOG("### CGrammarAnalyze::LogParserStatus End");
}

void CGrammarAnalyze::PopulateFirst()
{
    // build up the First Set of all the NonTerminate Tokens
    for (int i = 0; i != m_productions.size(); ++i)
    {
        if (m_First.find(m_productions[i]->Left()) == m_First.end())
        {
            set<Token_Type> First;
            m_First[m_productions[i]->Left()] = First;
        }
    }

    // do the following rules until all First Set is not growing
    // 1. if X is a terminate token, then First(X) = {X}
    // 2. if X is a non-terminate token and there exist a production of X->a..., then insert a into First(X);
    //    if there exist a production X->empty, insert empty into First(X)
    // 3. if there exist a production X-Y... and Y is a non-terminate token then add all non-empty element of First(Y)
    //    into First(X);
    //    if X->Y1Y2..Yn and Y1 to Yn are all non-terminate token ,and if to any j that 1<= j <= i - 1 , First(Yj) contains empty
    //    then add all non-empty element of First(Yi) into First(X)
    //    if all First(Yi) contain empty (j = 1,2,..,k) add empty into First(X)

    // Flag shows whether the sets has been changed
    bool SetChanged = false;
    // While the Sets are changing keep doing
    do
    {
        SetChanged = false;
        // for each production 
        for (int i = 0 ; i != m_productions.size(); ++i)
        {
            CProductionPtr pProdcution = m_productions[i];

            Token_Type LeftToken = pProdcution->Left();
            set<Token_Type>& FirstSet = m_First[LeftToken];
            
            // go through the left part of the production
            for (int j = 0; j != pProdcution->Length(); ++j)
            {
                Token_Type NextToken = pProdcution->Right()[j];

                if (IS_TERMINATE_TOKEN(NextToken))
                {
                    // if the NextToken is a terminate token
                    // add NextToken into FirstSet
                    SetChanged |= FirstSet.insert(NextToken).second;
                    break;
                }
                else
                {
                    // if the NextToken is non-terminate token
                    // add all the non-empty element in it's FirstSet into FirstSet
                    bool bContainEmpty = false;
                    for (set<Token_Type>::iterator it = m_First[NextToken].begin(); it != m_First[NextToken].end(); ++it)
                    {
                        if (*it == TOKEN_EMPTY)
                        {
                            bContainEmpty = true;
                            // we can get to the last position if all advance token contians
                            // empty in their First Set
                            if (j != pProdcution->Length() - 1)
                            {
                                continue;
                            }
                        }
                        SetChanged |= FirstSet.insert(*it).second;
                    }

                    if (!bContainEmpty)
                    {
                        break;
                    }
                }
            }
        }
    } while (SetChanged);


}

void CGrammarAnalyze::LogFirst()
{
    LOG("### CGrammarAnalyze::LogFirst Start");
    for (map<Token_Type, set<Token_Type> >::iterator it = m_First.begin(); it != m_First.end(); ++it)
    {
        Token_Type Token = it->first;
        set<Token_Type>& FirstSet = it->second;
        LOG("First(%s):", TOKEN_DEBUG_STRING(Token).c_str());

        for (set<Token_Type>::iterator sit = FirstSet.begin(); sit != FirstSet.end(); ++sit)
        {
            LOG("%s", TOKEN_DEBUG_STRING(*sit).c_str());
        }
    }
    LOG("### CGrammarAnalyze::LogFirst End");
}

bool CGrammarAnalyze::HasEmptyProduction( Token_Type Token )
{
    for (int i = 0; i != m_productions.size(); ++i)
    {
        CProductionPtr pProduction = m_productions[i];
        if (pProduction->Left() == Token && pProduction->Length() == 1 && pProduction->Right()[0] == TOKEN_EMPTY)
        {
            return true;
        }
    }

    return false;
}

void CGrammarAnalyze::LogFollow()
{
    LOG("### CGrammarAnalyze::LogFollow Start");
    for (map<Token_Type, set<Token_Type> >::iterator it = m_Follow.begin(); it != m_Follow.end(); ++it)
    {
        Token_Type Token = it->first;
        set<Token_Type>& FollowSet = it->second;
        LOG("Follow(%s):", TOKEN_DEBUG_STRING(Token).c_str());

        for (set<Token_Type>::iterator sit = FollowSet.begin(); sit != FollowSet.end(); ++sit)
        {
            LOG("%s", TOKEN_DEBUG_STRING(*sit).c_str());
        }
    }
    LOG("### CGrammarAnalyze::LogFollow End");
}

void CGrammarAnalyze::PopulateFollow()
{
    // build up the Follow Set of all the NonTerminate Tokens
    for (int i = 0; i != m_productions.size(); ++i)
    {
        if (m_Follow.find(m_productions[i]->Left()) == m_Follow.end())
        {
            set<Token_Type> Follow;
            m_Follow[m_productions[i]->Left()] = Follow;
        }
    }

    // do the following rules until none of the Follow Sets is growing
    // 1. for Start Token S, put End token into Follow(S)
    // 2. if there exist a production A->aBb, add all non-empty element in First(b) into Follow(B),
    //    and if b->empty, add all non-empty element in Follow(b) into Follow(B),
    // 3. if there exist a prodcution A->aB, or there exist a prodcution A->aBb and First(b) contains empty
    //    add all element in Follow(A) into Follow(B)

    m_Follow[TOKEN_START_EXTENSION].insert(TOKEN_EOF);

    bool bSetChanged = false;
    // while the Follow Sets are growing
    do 
    {
        bSetChanged = false;
        // for each production
        for (int i = 0; i != m_productions.size(); ++i)
        {
            bool FollowEmpty = true;
            CProductionPtr pProdcution = m_productions[i];
            Token_Type LeftToken = pProdcution->Left();
            
            set<Token_Type>& FollowSet = m_Follow[LeftToken];

            for (int TokenIndex = pProdcution->Length() - 1; TokenIndex >= 0; --TokenIndex)
            {
                Token_Type CurrentToken = pProdcution->Right()[TokenIndex];
                // if this is the last token in the production 
                // or the previous token 
                if (FollowEmpty)
                {
                    FollowEmpty = false;
                    if (IS_TERMINATE_TOKEN(CurrentToken))
                    {
                        if (CurrentToken == TOKEN_EMPTY)
                        {
                            FollowEmpty = true;
                        }
                    }
                    else
                    {
                        for (set<Token_Type>::iterator it = FollowSet.begin(); it != FollowSet.end(); ++it)
                        {
                            if (*it == TOKEN_EMPTY)
                            {
                                FollowEmpty = true;
                                continue;
                            }

                            bSetChanged |= m_Follow[CurrentToken].insert(*it).second;
                        }
                    }
                }

                
                // if there is a advance token
                if (TokenIndex != 0)
                {
                    Token_Type AdvanceToken = pProdcution->Right()[TokenIndex - 1];
                    if (IS_TERMINATE_TOKEN(AdvanceToken))
                    {

                    }
                    else
                    {
                        if (IS_TERMINATE_TOKEN(CurrentToken) && CurrentToken != TOKEN_EMPTY)
                        {
                            bSetChanged |= m_Follow[AdvanceToken].insert(CurrentToken).second;
                        }
                        else
                        {
                            for (set<Token_Type>::iterator it = m_First[CurrentToken].begin(); it != m_First[CurrentToken].end(); ++it)
                            {
                                if (*it == TOKEN_EMPTY)
                                {
                                    continue;
                                }

                                bSetChanged |= m_Follow[AdvanceToken].insert(*it).second;
                            }

                            if (HasEmptyProduction(CurrentToken))
                            {
                                for (set<Token_Type>::iterator it = m_Follow[CurrentToken].begin(); it != m_Follow[CurrentToken].end(); ++it)
                                {
                                    if (*it == TOKEN_EMPTY)
                                    {
                                        continue;
                                    }

                                    bSetChanged |= m_Follow[AdvanceToken].insert(*it).second;
                                }
                            }
                        }
                    }
                }
            }
        }
    } while (bSetChanged);
}

